package leetcode;

import java.util.Stack;

public class _20 {

	public static void main(String[] args) {
		new _20().isValid("dsa");
	}

	public boolean isValid(String s) {

		Stack<Character> stack = new Stack<>();

		char leftBracket1 = '(';
		char leftBracket2 = '[';
		char leftBracket3 = '{';

		char rightBracket1 = ')';
		char rightBracket2 = ']';
		char rightBracket3 = '}';

		char[] chars = s.toCharArray();

		for (char c : chars) {
			if (leftBracket1 == c || leftBracket2 == c || leftBracket3 == c) {
				stack.push(c);
			} else if (rightBracket1 == c || rightBracket2 == c
					|| rightBracket3 == c) {

				if (stack.isEmpty()) {
					return false;
				} else {
					Character left = stack.pop();
					if (rightBracket1 == c && left == leftBracket1) {
						continue;
					} else if (rightBracket2 == c && left == leftBracket2) {
						continue;
					} else if (rightBracket3 == c && left == leftBracket3) {
						continue;
					} else {
						return false;
					}

				}
			}
		}

		return stack.isEmpty();
	}

}
